package org.algorithm.熊猫.回溯算法;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 46. 全排列
 * 链接：https://leetcode-cn.com/problems/permutations/
 */
public class $4月24日$全排列 {


    @Test
    public void test(){
        System.out.println(permute(new int[]{0,1}));
    }


    public List<List<Integer>> permute(int[] nums) {

        if (nums.length == 0) {
            return res;
        }
        // 「路径」中的元素会被标记为 true，避免重复使⽤
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums,used);
        return res;
    }

    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    LinkedList<Integer> track = new LinkedList<>();


    // 回溯算法核⼼函数，遍历⼦集问题的回溯树
    void backtrack(int[] nums, boolean[] used) {

        //本次累加 路径和刚好等于目标target  退出
        if (nums.length==track.size()) {
            res.add(new LinkedList<>(track));
            return;
        }
        //记录前一个元素
     //   int preChar =  -1000;
        // 回溯算法标准框架
        for (int i = 0; i < nums.length; i++ ) {
            if (used[i]) {
                //当前数值已经在路径中
                continue;
            }
            //去重 ( 当前题不需要去重)
            //if(nums[i]==preChar){
              //  continue;
          //  }
          //  preChar=nums[i];
            // 做选择
            track.add(nums[i]);
            // 通过 used 参数控制经过的路径，避免路径走岔
            used[i] = true;
            backtrack(nums, used);
            // 撤销选择
            used[i] = false;
            track.removeLast();
        }
    }
}
